package zuoshen_video;

import java.util.*;

import org.junit.Test;

import utils.ArrayGenerator;

public class WindowProblems {

    //1. 滑动窗口的最大值
    /* 
        对于nums, 每个位置i计算从i到i + n - 1中的最大值，然后左右边界右移一位，放到res中，返回res
        最终的res的size应该是len - n + 1个
    */
    public int[] maxValueInWindow(int[] nums, int n) {
        int len = nums.length;
        //单调递减的双端队列
        Deque<Integer> deque = new LinkedList<>();
        for (int i = 0; i < n - 1; i++) {
            if (deque.isEmpty() || nums[i] < nums[deque.peekLast()]) deque.offerLast(i);
            else {
                while (!deque.isEmpty() && nums[deque.peekLast()] <= nums[i]) {
                    deque.pollLast(); //保持单调递减
                }
                deque.offerLast(i);
            }
        }
        int[] res = new int[len - n + 1];
        int idx = 0;
        for (int i = n - 1; i < len; i++) {
            if (!deque.isEmpty() && i - deque.peekFirst() == n) {
                //左边界过期
                deque.pollFirst();
            }
            if (deque.isEmpty() || nums[i] < nums[deque.peekLast()]) deque.offer(i);
            else {
                while (!deque.isEmpty() && nums[deque.peekLast()] <= nums[i]) {
                    deque.pollLast(); //保持单调递减
                }
                deque.offerLast(i);
            }
            //左边界即为窗口最大值
            res[idx++] = nums[deque.peekFirst()];
        }
        return res;
    }

    @Test
    public void test1() {
        int[] nums = ArrayGenerator.getArray(20, 10);
        System.out.println(Arrays.toString(nums));
        int[] res = maxValueInWindow(nums, 3);
        System.out.println(Arrays.toString(res));
    }

    //2. 查找数组每个位置左右两边最近的比他大的数，若不存在，设为-1
    public List<int[]> getNearestMax(int[] nums) {
        int len = nums.length;
        Deque<Integer> deque = new LinkedList<>();
        
        int[] t;
        List<int[]> res = new ArrayList<>();
        for (int i = 0; i < len; i++) {
            t = new int[2];
            while (!deque.isEmpty() && nums[deque.peekLast()] <= nums[i]) deque.pollLast();
            t[0] = deque.isEmpty() ? -1 : nums[deque.peekLast()];
            deque.offer(i);
            res.add(t);
        }

        deque.clear();
        for (int i = len - 1; i >= 0; i--) {
            t = res.get(i);
            while (!deque.isEmpty() && nums[i] >= nums[deque.peekLast()]) deque.pollLast();
            t[1] = deque.isEmpty() ? -1 : nums[deque.peekLast()];
            deque.offerLast(i);
        }
        return res;
    }

    //优化方法，只需要一趟遍历即可
    public List<int[]> getNearestMax1(int[] nums) {
        int len = nums.length;
        Deque<LinkedList<Integer>> deque = new LinkedList<>();
        
        int[] t;
        List<int[]> res = new ArrayList<>();
        int right;
        for (int i = 0; i < len; i++) {
            right = nums[i];
            while (!deque.isEmpty() && nums[deque.peekLast().getLast()] < nums[i]) {
                LinkedList<Integer> list = deque.pollLast();
                for (int j = 0; j < list.size(); j++) {
                    t = new int[2];
                    t[0] = deque.isEmpty() ? -1 : nums[deque.peekLast().getLast()];
                    t[1] = right;
                    res.add(t);
                }
                right = nums[list.getLast()];
            }
            if (deque.isEmpty() || nums[deque.peekLast().getLast()] > nums[i]) {
                LinkedList<Integer> list = new LinkedList<>();
                list.add(i);
                deque.offerLast(list);
            } else deque.peekLast().addLast(i);
        }

        right = -1;
        while (!deque.isEmpty()) {
            LinkedList<Integer> list = deque.pollLast();
            for (int j = 0; j < list.size(); j++) {
                t = new int[2];
                t[0] = deque.isEmpty() ? -1 : nums[deque.peekLast().getLast()];
                t[1] = right;
                res.add(0, t);
            }
            right = nums[ list.getLast()];
        }
        return res;
    }
 
    @Test
    public void test2() {
        int[] nums = ArrayGenerator.getArray(20, 10);
        System.out.println(Arrays.toString(nums));
        List<int[]> res = getNearestMax(nums);
        List<int[]> res2 = getNearestMax1(nums);
        for (int i = 0; i < res.size(); i++) {
            System.out.println(Arrays.toString(res.get(i)));
            System.out.println(Arrays.toString(res2.get(i)));
            System.out.println("==========================");
        }
    }


    /* 
        指标A：任何一个子数组【包括自己】和与数组最小值的乘积
        返回nums中最大的指标A

        要求数组全为正数
    */
    public int maxQuotaA(int[] nums) {
        int max = Integer.MIN_VALUE, len = nums.length, lo = 0, hi = 0, min = 0, sum = 1;
        int[] t;
        List<int[]> res = new ArrayList<>();
        Stack<Integer> stack = new Stack<>();
        for (int i = 0; i < len; i++) {
            //相等也需要出栈，相等说明不了左边界
            while (!stack.isEmpty() && nums[stack.peek()] <= nums[i]) stack.pop();
            stack.push(i);
            t = new int[2];
            t[0] = stack.isEmpty() ? 0 : stack.peek();
            res.add(t);
        }
        stack.clear();
        for (int i = len - 1; i >= 0; i--) {
            while (!stack.isEmpty() && nums[stack.peek()] <= nums[i]) stack.pop();
            stack.push(i);
            t = res.get(i);
            t[1] = stack.isEmpty() ? (len - 1) : stack.peek();
        }
        for (int i = 0; i < res.size(); i++) {
            t = res.get(i);
            lo = t[0];
            hi = t[1];
            // for (int i = 0)
        }
        return 0;
    }

    public int maxQuotaA1(int[] nums) {
        int max = Integer.MIN_VALUE, len = nums.length;
        int[][] f = new int[len][len];
        for (int i = 0; i < len; i++) {
            
        }
        return 0;
    }
}
